package com.demo.controller;

import com.demo.model.Board;

import java.util.HashMap;
import java.util.Map;

/**
 * 计算卡片移动方案的类
 */
public class MoveSolution {
    /**
     * 四个方向的向量
     */
    private static final int[][] DIRECTIONS = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

    /**
     * 描述“上”方向
     */
    public static final int UP = 0;

    /**
     * 描述“左“方向
     */
    public static final int LEFT = 1;

    /**
     * 描述”下”方向
     */
    public static final int DOWN = 2;

    /**
     * 描述“上”方向
     */
    public static final int RIGHT = 3;

    private final static int m = Board.rows;
    private final static int n = Board.cols;

    /**
     * 当前方案要计算的方向
     */
    private final int direction;

    /**
     * 当前方案要计算的所有卡片的邻接矩阵
     */
    private final int[][] grid;

    /**
     * 新卡片标记矩阵
     */
    private final boolean[][] isNew = new boolean[m][n];

    /**
     * 深度优先搜索记忆化用缓冲
     */
    private final Map<Integer, Integer> cache;

    /**
     * 存放所有卡片的起点和终点
     */
    private final Map<Integer, Integer> moveMap;
    private int score;

    public MoveSolution(int direction) {
        this.direction = direction;
        Board b = Board.getInstance();
        score = b.getScore();
        grid = CardsHandler.copyGrid(b.getGrid());
        moveMap = new HashMap<>();
        cache = new HashMap<>();
    }

    /**
     * start moving!!
     *
     * @return false if no card could be moved
     */
    public boolean move() {
        if (!isCouldMove()) {
            return false;
        }
        // backup somethings before start
        BackWardListener.getInstance().prepareToBack();
        // update the grid
        Board.getInstance().setGrid(grid);
        CardsHandler.getInstance().nextRound(direction, moveMap, score);
        return true;
    }

    /**
     * 判断是否存在任何能够移动的卡片
     *
     * @return 返回 true 如果存在
     */
    public boolean isCouldMove() {
        return !getMoveMap().isEmpty();
    }

    /**
     * 返回一个存储所有卡片的“起点”和“终点”的map
     *
     * @return a map contains "from" -> "to" for moved cards
     */
    private Map<Integer, Integer> getMoveMap() {
        if (!moveMap.isEmpty()) {
            return moveMap;
        }
        Board.getInstance().getCards().forEach(card -> dfs(card.getRow(), card.getColumn()));
        // 过滤“没有移动”的键值对，其余存储到另外的Map中
        cache.forEach((from, to) -> {
            if (!from.equals(to)) {
                moveMap.put(from, to);
            }
        });
        return moveMap;
    }

    /**
     * 深度优先搜索
     * <p>
     * 以direction为前进方向进行搜索，返回从第i行、j列开始能够到达的位置——遇到的第一张卡片的位置或者边界。
     * <p>
     * 该位置可能包含卡片，或者没有，又或者该位置和现在一致，表示无法继续往前。
     * <p>
     * 假如当前位置正有一张卡片，则该卡片会尝试移动到“实际目的地”，“实际目的地”由下面三种情况决定。
     * <li>如果目的地存在一张卡片，并且数字与当前卡片的数字不一致，则“实际目的地”要后退一步。</li>
     * <li>如果目的地存在一张卡片，数字一致，并且该卡片不是”新合成的“，则“实际目的地”不变。</li>
     * <li>如果目的地没有卡片，则“实际目的地不变”</li>
     * <p>
     * 两个相同的卡片（数字一致）合并时，将被标记为”新合成”
     * <p>
     *
     * @param i 行
     * @param j 列
     * @return 返回从第i行、j列开始能够到达的目的地的位置。
     */
    private int dfs(int i, int j) {
        // recursion stop
        if (i == -1) {
            return j;
        } else if (i == n) {
            return (i - 1) * m + j;
        } else if (j == -1) {
            return i * m;
        } else if (j == m) {
            return i * m + j - 1;
        }

        // return the position from our memory map
        if (cache.containsKey(i * m + j)) {
            return cache.get(i * m + j);
        }
        // final position of next card
        int pos = dfs(i + DIRECTIONS[direction][0], j + DIRECTIONS[direction][1]);

        // if there is exactly a card at here.
        if (grid[i][j] != 0) {
            int i1 = pos / m;
            int j1 = pos % m;
            int number = grid[i][j];
            // 如果目标处存在一张卡片
            if (grid[i1][j1] != 0) {
                // 如果数字不同
                if (grid[i1][j1] != number || isNew[i1][j1]) {
                    // 真正目标目标位置为原位置“退一步”
                    pos += -DIRECTIONS[direction][0] * m - DIRECTIONS[direction][1];
                    i1 = pos / m;
                    j1 = pos % m;
                } else {
                    number *= 2;
                }
            }
            // 检查是否回到原地
            if (!(i == i1 && j == j1)) {
                // 标记，产生新卡片
                if (grid[i1][j1] * 2 == number) {
                    isNew[i1][j1] = true;
                    // 产生加分
                    score += number;
                }
                // 移动（交换）
                grid[i1][j1] = number;
                grid[i][j] = 0;
            }
            cache.put(i * m + j, pos);
        }
        return pos;
    }

    // 游戏结束检测
    public static boolean isGameOver() {
        Board b = Board.getInstance();
        final int maxSize = Board.rows * Board.cols;
        boolean isFull = b.getCards().size() == maxSize;
        if (!isFull) {
            return false;
        }
        // 检查是否有下一次移动
        int[] dirs = {UP, RIGHT, DOWN, LEFT};
        for (int dir : dirs) {
            MoveSolution test = new MoveSolution(dir);
            if (test.isCouldMove()) {
                return false;
            }
        }
        return true;
    }

    /**
     * 返回方向向量在x的分量
     * <p>
     * 与get_dy()一样，这两个公开的方法是为了给MovingCard线程在绘制卡片移动时提供数值计算的
     * <p>
     *
     * @param direction 指定的方向
     * @return x的分量
     */
    public static int get_dx(int direction) {
        return DIRECTIONS[direction][1];
    }

    /**
     * 返回方向向量在y的分量
     *
     * @param direction 指定的方向
     * @return y的分量
     */
    public static int get_dy(int direction) {
        return DIRECTIONS[direction][0];
    }
}
